/**
 * Copyright (C) 2007 Stefan Buettcher. All rights reserved.
 * This is free software with ABSOLUTELY NO WARRANTY.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA
 **/

/**
 * Implementation of the @cdr query: Cover Density Ranking.
 *
 * Sort passages within document by length (ascending). Put decay in front
 * of every passage score (decay=0.5). If length of passage < KAPPA, score
 * is WEIGHT, else WEIGHT / (KAPPA / len).
 *
 * author: Stefan Buettcher
 * created: 2005-10-12
 * changed: 2007-06-18
 **/


#include <assert.h>
#include <math.h>
#include <string.h>
#include "cdrquery.h"
#include "getquery.h"
#include "querytokenizer.h"
#include "../misc/all.h"


const double CDRQuery::DEFAULT_K;
const int CDRQuery::CDR_MAX_SCORER_COUNT;
const int CDRQuery::DEFAULT_MAX_LEVEL;


void CDRQuery::initialize(Index *index, char *command, char **modifiers, char *body,
		VisibleExtents *visibleExtents, int memoryLimit) {
	this->index = index;
	this->visibleExtents = visibleExtents;
	this->memoryLimit = memoryLimit;
	processModifiers(modifiers);
	queryString = duplicateString(body);
	actualQuery = this;
	ok = false;
} // end of initialize(Index*, char*, char**, char*, VisibleExtents*, int)


CDRQuery::CDRQuery() {
	mustFreeVisibleExtentsInDestructor = false;
} // end of CDRQuery()


CDRQuery::CDRQuery(Index *index, char *command, char **modifiers, char *body,
		VisibleExtents *visibleExtents, int memoryLimit) {
	initialize(index, command, modifiers, body, visibleExtents, memoryLimit);
	mustFreeVisibleExtentsInDestructor = false;
} // end of CDRQuery(...)


CDRQuery::CDRQuery(Index *index, char *command, char **modifiers, char *body,
		uid_t userID, int memoryLimit) {
	this->userID = userID;
	VisibleExtents *visibleExtents = index->getVisibleExtents(userID, false);
	initialize(index, command, modifiers, body, visibleExtents, memoryLimit);
	mustFreeVisibleExtentsInDestructor = true;
} // end of CDRQuery(...)


CDRQuery::~CDRQuery() {
} // end of ~CDRQuery()


bool CDRQuery::parse() {
	// if no container is given, assume default container
	char defaultContainer[MAX_CONFIG_VALUE_LENGTH];
	if (!getConfigurationValue("DEFAULT_RETRIEVAL_SET", defaultContainer))
		strcpy(defaultContainer, DOC_QUERY);

	if (!parseQueryString(queryString, defaultContainer, NULL, memoryLimit)) {
		syntaxErrorDetected = finished = true;
		ok = false;
	}
	else if (((elementCount < 1) || (elementCount > CDR_MAX_SCORER_COUNT)) && (maxLevel > 1)) {
		// @cdr queries may not contain more than CDR_MAX_SCORER_COUNT query terms
		syntaxErrorDetected = finished = true;
		ok = false;
	}
	else {
		if (statisticsQuery == NULL)
			if (visibleExtents != NULL)
				statisticsQuery = new GCLQuery(index, visibleExtents->getExtentList());
		processQuery();
		ok = true;
	}
	return ok;			
} // end of parse()


void CDRQuery::processCoreQuery() {
	offset start, end, s, e;
	ExtentList *elementLists[MAX_SCORER_COUNT];
	ExtentList *containerList = containerQuery->getResult();
	ExtentList *statisticsList = statisticsQuery->getResult();

	assert(((elementCount >= 1) && (elementCount <= CDR_MAX_SCORER_COUNT)) || (maxLevel == 1));

	double documentCount = containerList->getLength();
	if (documentCount < 1) {
		// no matching container found: stop execution
		count = 0;
		return;
	}

	// compute IDF values
	for (int i = 0; i < elementCount; i++) {
		elementLists[i] = elementQueries[i]->getResult();
		ExtentList_Containment list(
				new ExtentList_Copy(statisticsList), new ExtentList_Copy(elementLists[i]), false, false);
		internalWeights[i] = MAX(0, externalWeights[i] * log(1E12 / list.getLength()));
	}

	double subsetWeights[1 << CDR_MAX_SCORER_COUNT];
	ExtentList *subsets[1 << CDR_MAX_SCORER_COUNT];
	int subsetCnt = 0;
	if (maxLevel <= 1) {
		ExtentList **lists = typed_malloc(ExtentList*, elementCount);
		for (int i = 0; i < elementCount; i++)
			lists[i] = new ExtentList_Copy(elementLists[i]);
		subsets[subsetCnt] = new ExtentList_AND(lists, elementCount);
		subsetWeights[subsetCnt] = 1;
		subsetCnt++;
	}
	else {
		for (int k = 1; k < (1 << elementCount); k++) {
			ExtentList **lists = typed_malloc(ExtentList*, elementCount);
			int listCnt = 0;
			double totalWeight = 0;
			for (int i = 0; i < elementCount; i++) {
				if (k & (1 << i)) {
					lists[listCnt++] = new ExtentList_Copy(elementLists[i]);
					totalWeight += internalWeights[i];
				}
			}
			assert(listCnt > 0);
			subsets[subsetCnt] = new ExtentList_AND(lists, listCnt);
			subsetWeights[subsetCnt] = totalWeight;
			subsetCnt++;
		}
	}

	// sort subsets by IDF value; we can afford to use BubbleSort here,
	// because subsetCnt is small
	bool changed = true;
	while (changed) {
		changed = false;
		for (int i = 0; i < subsetCnt - 1; i++) {
			if (subsetWeights[i] < subsetWeights[i + 1]) {
				double ssw = subsetWeights[i];
				subsetWeights[i] = subsetWeights[i + 1];
				subsetWeights[i + 1] = ssw;
				ExtentList *ss = subsets[i];
				subsets[i] = subsets[i + 1];
				subsets[i + 1] = ss;
				changed = true;
			}
		}
	}

	// initialize heap structure
	ScoredExtent candidate;
	results = typed_malloc(ScoredExtent, count + 1);
	int resultCount = 0;

	// prune the search by only looking at documents that might contain
	// interesting information; "nextOffsetPossible" contains the next
	// index position at which we can find a query element
	offset nextOffsetPossible = MAX_OFFSET;
	offset elemStart, elemEnd;
	for (int elem = 0; elem < elementCount; elem++)
		if (elementLists[elem]->getFirstEndBiggerEq(0, &elemStart, &elemEnd))
			if (elemEnd < nextOffsetPossible)
				nextOffsetPossible = elemEnd;

	while (containerList->getFirstEndBiggerEq(nextOffsetPossible, &start, &end)) {
		double docLen = (end - start + 1);
		candidate.from = start;
		candidate.to = end;
		candidate.score = 0;

		// find best subset matching this document and compute CDR score
		for (int i = 0; (i < subsetCnt) && (i < maxLevel); i++) {
			s = start - 1;
			while (subsets[i]->getFirstStartBiggerEq(s + 1, &s, &e)) {
				if (e > end)
					break;
				candidate.score += MIN(1, K / (e - s + 1));
			}
			if (candidate.score > 0) {
				candidate.score += 1000 * (subsetCnt - i);
				break;
			}
		}

		if (candidate.score > 0)
			addToResultSet(&candidate, &resultCount);

		// find next document that could possibly contain one of the query terms
		nextOffsetPossible = MAX_OFFSET;
		for (int elem = 0; elem < elementCount; elem++)
			if (elementLists[elem]->getFirstEndBiggerEq(start + 1, &elemStart, &elemEnd))
				if (elemEnd < nextOffsetPossible)
					nextOffsetPossible = elemEnd;
		if (nextOffsetPossible < end + 1)
			nextOffsetPossible = end + 1;
	} // end while (containerList->getFirstEndBiggerEq(nextOffsetPossible, &start, &end))

	// free memory allocated for query term sets
	for (int i = 0; i < subsetCnt; i++)
		delete subsets[i];

	count = resultCount;
} // end of processCoreQuery()


void CDRQuery::processModifiers(char **modifiers) {
	RankedQuery::processModifiers(modifiers);
	K = MAX(1, getModifierDouble(modifiers, "k", DEFAULT_K));
	maxLevel = MAX(1, getModifierInt(modifiers, "maxlevel", DEFAULT_MAX_LEVEL));
	if (getModifierBool(modifiers, "strict", false))
		maxLevel = 1;
} // end of processModifiers(char**)


